This invention relates to computer processing in general, and more particularly to a method and system for image processing. The patent application claims priority of French patent application No. 93.03455, filed Mar. 25, 1993, the contents of which are herein incorporated by reference.
The present invention was created in response to the shortcomings of the current generation of image retouching systems. Other retouching systems use one of two methods for handling images: (1) high resolution/low resolution (high res/low res), and (2) virtual image. Each of these two approaches overcomes some major obstacles, however neither fully responds to the needs of today""s color professionals for high quality, and fast response at an affordable price.
In the high res/low res approach, the complete scanned image (referred to as the xe2x80x9chigh resxe2x80x9d image) is subsampled to yield a much smaller image (referred to as the xe2x80x9clow resxe2x80x9d image). Because previous image retouching systems did not yield xe2x80x9creal timexe2x80x9d performance when handling large images (over 10M or 10 million bytes), it was necessary to invent an approach to allow the retouching system work on a smaller, i.e. low res image that would yield acceptable response times for the operator. Using this approach, retouching actions are stored in a script. When retouching is complete, the script is typically passed to a more powerful, and expensive, server and xe2x80x9cexecuted.xe2x80x9d That is, the actions contained in the script are applied to the high res image, which results in a high quality final image. The disadvantage of this approach is that the operator does not work with the actual image or at highly detailed levels (particularly for a magnified xe2x80x9cclose-upxe2x80x9d of a portion). As a result, it is not always possible to perform highly detailed retouching actions such as silhouetting and masking. Moreover, unpleasant surprises may occur upon execution.
The virtual image approach, commonly used by desktop image editing packages (e.g. MacIntosh or Windows types), manipulates a copy of the actual image held in memory. In some cases, one or more copies or intermediate drafts are held, enabling the user to revert to a previous copy if an error is introduced. Using the virtual image approach, the image itself is transformed as retouching effects are applied.
The virtual image approach suffers two important shortcomings: first, large amounts of memory are required; and second, each effect is applied immediately to the entire image so that complex manipulation, such as large airbrushing, scaling and rotation, incur long processing delays.
Prior image retouching systems have used large mainframe computers or work stations and proprietary hardware. For example, U.S. Pat. No. 5,142,616, issued Aug. 25, 1992 to Kellas, et al., teaches an electronic graphic system. In this system, data relating to a user-defined low resolution image functions to control an image by the combining other image data with data defining a low resolution representation of the initial image. Once desired modifications have been achieved, the image is displayed on a display monitor so that a low resolution control image is converted to a high resolution representation. Stapleton, et al., U.S. Pat. No. 4,775,858, issued Oct. 4, 1988, also teaches the use of a large frame store to produce an image of higher resolution than that found on a television screen.
Due to the high amount of memory required for processing, personal computers have proven very slow and marginally acceptable. Moreover, even with larger mainframe systems, there is not always a good correlation between the monitor and the printed image since there is not always a way to visualize the final image on the display device. Thus, discrepancies can be introduced due to differences between screen resolution and print resolution. Other relevant patents include: U.S. Pat. No. 5,179,651 issued Jan. 12, 1993 to Taaffe, et al., U.S. Pat. No. 5,065,346, issued Nov. 12, 1991 to Kawai, et al., U.S. Pat. No. 4,656,467, issued Apr. 7, 1987 to Strolle, U.S. Pat. No. 4,833,625, issued May 23, 1989 to Fisher, et al., U.S. Pat. No. 4,288,821, issued Sep. 8, 1991 to Lavallee, et al., and U.S. Pat. No. 4,546,385, issued Oct. 8, 1985 to Anastassiou.
Numerous image processing procedures currently exist. Common to all procedures is modification of an image through recalculation operations to irreversibly rearrange dots or picture elements (xe2x80x9cpixelsxe2x80x9d) of an original image (or those resulting from the most recent modification) into a new arrangement.
Perhaps the greatest disadvantage of known procedures stems from the image that is displayed on the monitor not being identical to the image that will eventually be printed, rendering the operator unable to see the work as it will actually appear in print. Anomalies and discrepancies can therefore occur in the printed image. Known procedures cannot resolve the fact that the image displayed on the operator""s monitor screen is in most cases vastly less defined than the scanned image held in the computer""s memory. (This is untrue only in the case of small, low resolution images.) Resolution (as measured in dots per inch) of modern display monitors is far less than the resolution of printed color images.
A second and perhaps equally important disadvantage of known image processing techniques is that the image editing effects are applied sequentially, i.e. step-by-step. This incurs a severe degradation in the quality of the original image if many image editing effects are applied to the same portion of an image.
Operations carried out on an image usually require a high degree of processing power. If processing power is unavailable, then the time required to carry out the operation becomes unacceptably long, thus reducing the scope and sophistication of possible operations to be carried out on the image. For example, airbrush strokes are currently extremely limited in size as a result of the extreme processing power needed to calculated image changes.
The irreversible nature of image processing using known procedures precludes the operator from easily implementing any second thoughts. Presently, the only way to correct an airbrush stroke which does not achieve a desired effect is to superimpose a new stroke (instead of merely erasing the unsuccessful stroke). Alternatively, computers equipped with large memory can save intermediate steps. However, this requires a huge amount of memory (e.g., a single 8xc2xdxe2x80x3xc3x9711xe2x80x3xc3x97300 dots per inch (dpi) figure requires over 33 million bytes).
The present invention overcomes these shortcomings and permits rapid and powerful editing functions even on less powerful desktop computers, by employing at least one, more preferably two and most preferably three new and independent processes: preprocessing, image editing, and raster image processing.
The subject invention advantageously uses what I call a Functional Interpolating Transfer System (FITS) to greatly speed editing of an image on standard microcomputers, thus eliminating the need for expensive workstations or special hardware. FITS breaks down image processing into three steps: preprocessing, image editing and FITS raster image processing. This results in a virtually instantaneous response and eliminates waiting for file saving or processing updates. With this technique, limits on file size and resolution disappear.
Preprocessing in the invention (brand name xe2x80x9cFITSxe2x80x9d) involves creating a specially formatted version of an image which allows image editing to progress at rapid speed.
Image editing refers to the process of retouching, combining or otherwise modifying images, to create the final desired image. Image editing involves, in the broadest sense, all processing operations performed on an original image. This includes the combining of images, effects such as sharpening, blurring, brightening, darkening, distortion, and include modifications to the color or appearance of all or part of a original image.
Color changes may be achieved in a variety of ways including global changes to the chromatic range of the image, or selective change to individual colors, e.g. changing blue to red.
Raster image processing (xe2x80x9cRIPxe2x80x9d) is performed in two instances: (1) each time a new screen view is generated for display on a monitor, and (2) when an output page is generated for the purpose of printing or incorporated into another system such as a desktop publishing system. FITS raster image processing combines the input images with the modifications generated in the second stage (image editing) to create either a screen or print image. The output image generated by the FITS RIP can have any resolution; thus it is said to be resolution independent.
FITS raster image processing (xe2x80x9cFITS RIPxe2x80x9d) involves taking the ensemble of image manipulations (the various steps or xe2x80x9clayersxe2x80x9d of changes) that are performed during the image editing process and computing a single image for purposes of printing or display on a monitor. Modifications to the image, made during image editing, are characterized in a manner that is independent of the resolution of the input images or final output image. During a FITS RIP, layers are first combined mathematically for each pixel or selected pixels in the desired image, rather than by applying each layer successively to the original images. For each final pixel, a single mathematical function is generated that describes the color, in an arbitrary color space, at that point. If, as preferred, only a sample of pixels are fully computed for each layer of change, the color values of intermediate pixels are computed by averaging the mathematical functions of the neighboring pixels and applying that function average to the original pixel""s color, rather than simply averaging the color values of the surrounding pixels. This approach results in a time savings in overall image handling and a higher quality resulting image.
In the FITS approach, the image editing actions are characterized by parameters to mathematical functions and these are stored layer-by-layer in a file separate from the original image(s). Each intermediate modification to the image is effectively saved in a layer and each layer can be independently modified, deleted or reordered. The parameters can be stored for points in a grid that is itself independent of the xe2x80x9cdots-per-inchxe2x80x9d resolution (dpi) of either the original imported images, or the final output images. As a result, images for display or print can be generated at an arbitrary resolution.
Substantially less memory is required during image editing than with the virtual image approach since only the changes to each layer are stored, not entire image each time. As a result, a sophisticated, heavily retouched new image consisting of over 10 layers can be described in a FITS file of 2-5 megabytes (2-5M), as compared with over 30M (megabytes) for existing virtual image systems to store a 1 page new image (at 300 dpi resolution). Thus, the FITS approach yields a 10 to 1 average savings per page of image, and substantially more for larger images or higher resolutions. Note that 600 dpi images are now quite common for high quality publishing, and this is likely to increase in the future.
To sum up, current computerized image processing for obtaining a high definition image suffers from the dual disadvantages of requiring extremely high processing power, a limitation of productivity and creativity for the operator due to the irreversibility of image editing steps, and the quality restrictions inherent in a pixel-based approach.
The subject invention, on the other hand, provides a computerized image processing procedure which enables the operator to rapidly carry out advanced graphic operations, and to reverse decisions as requiredxe2x80x94without in any way affecting the definition or precision of the final image.
The invention provides an image processing system for the creating and editing images that are resolution independent and characterized by a series of layers, or image objects, that can be combined together to yield an output image, at any resolution, for display or print. The new method of image processing in a computerized system creates a high performance image representation, that yields much faster image processing by supplying data defining an original image into the system and reorganizing the original image data.
One aspect of this method (pre-processing, which I call xe2x80x9cIVUExe2x80x9d format) comprises the following steps: (1) supplying data defining the original image into the system, (2) assigning pixels from the original image to pixels in the new image format in such a way that the new image is organized in groups (preferably rectangles and most preferably squares), each of which can be individually compressed (using JPEG or another compression algorithm) to yield reduced image size and faster access over a network, (3) creating a second, lower resolution, image by averaging groups of pixels falling within a first predetermined area (or neighborhood) into an averaged pixel, and performing this computation across the entire original image; this second image is also organized in groups, e.g. squares, (4) repeating the previous step, and thereby creating succession of decreasing resolution images, which are stored adjacent to the first two, until a number of pixels less than or equal to a preselected number of pixels remain, and (5) saving the resulting image representation on a storage device.
Also provided is a method for image processing in a computerized system that involves applying changes to one or more original images as a series of xe2x80x9clayersxe2x80x9d in which the changes are recorded as resolution-independent mathematical functions. This approach has the property that only the final result of the retouching effects in a layer needs to be calculated or characterized and the effects are wholly or partially reversible. The layers themselves are independent and may at any time be modified, deleted, or reordered. The changes in each layer are generally characterized in a way that is independent of resolution.
This aspect of the method comprises the following steps: (1) for a layer 1, 2, 3, etc., generally number xe2x80x9cixe2x80x9d, displaying the results of the image processing up to and including all effects applied and original effects inserted for the xe2x80x9cixe2x88x921xe2x80x9dth layer (e.g. 5th layer) (2) recording all effects applied in the ith layer (e.g. 6th layer) as parameters to mathematical functions that define the effect, so that for each pixel in the displayed image that is modified there is a single function that describes the resulting modification, (3) when the operator terminates processing of the ith layer these parameters are saved along with the parameters that describe changes to the preceding ixe2x88x921 layers.
Also provided is a method for image processing in a computerized system that enables a raster image to be computed, either with the ability of displaying the image on a computer monitor or for printing the image.
This method involves: (1) sampling an original image to be processed with a definition grid so as to retain a predetermined number of dots from all of the dots contained within the original image, the predetermined number being equal to or less than the number required to either display the result on a computer monitor or to generate an output file destined to be printed; and (2) for each dot in the grid to generate a single mathematical function that represents the cumulative effect of all the layers in the image at that point. This is done by processing the resulting image into elementary recurrent operations each broken down into three parts and providing, based on the result of the previous elementary operation, these three parts added to each other, (3) filling in sufficient additional dots, or pixels, within the grid to reach the required resolution for screen or print by interpolating the functions at the surrounding gridpoints to obtain a single function that can be applied to intermediate pixels and will yield an interpolated color value for that pixel, (4) computing the color value results for each pixel, and (5) either printing or displaying the result, or storing the result on a computer storage device.
The invention may use a method of image processing in a computerized system, comprising: (a) supplying data defining an original image into the system, (b) assigning pixels from the original image to pixels in a new first image format so that the first image is organized into groups of pixels, each of the groups being individually compressible to yield a reduced size image, and (c) reducing the number of assigned pixels to form a reduced resolution image by averaging (preferably using a Gaussian function to weight the average for pixel proximity) a particular number of adjacent pixels falling within a first (preferably predetermined) area into a first averaged pixel, organized by the groups of pixels, and performing this computation across the entire first image format, to form a reduced definition image.
This method may (and preferably does) further comprise reducing the number of the first averaged pixels by averaging groups of pixels falling within a second predetermined area into a second averaged pixel, organized by the groups of pixels, performing this computation across the entire second image format, and (preferably) repeating this step until a preselected or lower number of pixels remain, the remaining pixels forming a reduced definition image. Data defining the reduced definition image may be modified by a user to obtain a desired result and the system or user may save a copy of the data or mathematical functions defining the pixels that form the desired result. Moreover, the data defining the original image may be added to the data defining the pixels forming the desired result, and forming an image from the added data.
The invention may also include a method of raster image processing which includes: (a) adding data defining an original image to data defining modifications to a reduced definition image, and (b) forming an image from the added data. Preferably, this is accomplished by a computerized system which comprises: (a) means for adding data defining pixels forming an original image to data defining modifications to a reduced definition image, and (b) means for forming an image from the added data.
The invention may also include a computerized system for image processing, comprises: (a) means for assigning pixels from an original image to pixels in a new first image format so that the first image is organized into compressible groups of pixels, and (b) means for reducing the number of assigned pixels to form a reduced resolution image by averaging a particular number of adjacent pixels falling within a first (preferably predetermined) area into a first averaged pixel, organized across the entire first image format, to form a reduced definition image. Preferably, means are provided for reducing the number of the first averaged pixels by averaging groups of pixels falling within a second predetermined area into a second averaged pixel, organized by the groups of pixels, performing this computation across the entire image format, and repeating this step until a preselected number of pixels remain, the remaining pixels forming a final reduced definition image.